import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-10-13
 * Time: 18:41
 */
public class BinaryTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }

    public int i=0;
    public TreeNode buildTree(int[] pre,int[] in,int begin,int end){
        if(begin > end){
            return null;
        }
        TreeNode root=new TreeNode(pre[i]);
        int orderIndex=getInOrderIndex(in,pre[i],begin,end);
        i++;
        root.left=buildTree(pre,in,begin,orderIndex-1);
        root.right=buildTree(pre,in,orderIndex+1,end);
        return root;
    }
    private int getInOrderIndex(int[] in, int val, int begin, int end) {
        for (int j = begin; j <= end; j++) {
            if(in[j]==val){
                return j;
            }
        }
        return -1;
    }

    public void levelOrder(int[] pre,int[] in,int begin,int end){
        TreeNode root=buildTree(pre, in, begin, end);
        levelOrderChild(root);
    }

    public void levelOrderChild(TreeNode root){
        ArrayList<Integer> arrayList=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size=queue.size();
            while(size > 0) {
                TreeNode cur = queue.poll();
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }

                if(size == 1){
                    arrayList.add(cur.val);
                }
                size--;
            }
        }
        //System.out.println(arrayList);
        Iterator<Integer> iterator=arrayList.iterator();
        while(iterator.hasNext()){
            System.out.print(iterator.next()+" ");
        }
    }


    public TreeNode prev=null;

    public void convertBSTToDoublyLinkedList(TreeNode root){
        if(root == null){
            return;
        }
        convertBSTToDoublyLinkedList(root.left);
        root.left=prev;
        if(prev!=null){
            prev.right=root;
        }
        prev=root;
        convertBSTToDoublyLinkedList(root.right);
    }

    public TreeNode func(TreeNode root){
        if(root == null){
            return null;
        }
        convertBSTToDoublyLinkedList(root);
        while(root.left != null){
            root=root.left;
        }
        return root;
    }
}
